題目

題目給予了 singly-linked list中node的定義
每個node有一個key與指向下個node的指標。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

請寫一個function，輸入參數為node的指標，不回傳，要做到把這個輸入的node刪除。

singly-linked list

將多個node串接起來，就成了linked list，因為node只有指向下個node的指標，被稱作singly-linked list。
如圖所示:

特點

• 不一定需要一個連續的空間
• 相對於array，插入與刪除快速
  • array是一次分配一個連續的空間來儲存資料，刪除中間的值(這裡不是指刪掉值而已，而是把空間還給OS)需要重新分配空間，較為費時
• 搜索較慢，須從頭循序查找
  • Time complexity O(n)

解法

因為規定function的輸入參數是要刪除的node，沒辦法直接改前一個node的next，。
但我們能換個方式，思路是把要刪除的node改成原本的下一個。
1. 把下個node的value覆寫到這個node。
2. 用一個tmp pointer儲存下個node(等下要釋放記憶體)
3. 調整pointer
如圖所示:

class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* tmp = node->next;
        node->val = node->next->val;
        node->next = node->next->next;
        delete tmp;
    }
};